/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue> 
#include <stack>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
#include<numeric>  // 用于对vector求和----accumulate函数
// #define NDEBUG
#include <assert.h>
using namespace boost;   // 支持string的操作
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

// 遍历
template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit_arr(vector<T>& arr, string const str){
    cout << str << ": ";
    // typename T::const_iterator it = arr.begin();
    for(auto it=arr.begin();it!=arr.end();++it){
        cout << *it <<" ";
    }
    cout<<endl;
}

// 遍历
// template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
void visit2_arr(vector<int>& arr, string const str){
    cout << str << ": ";
    for(int i; i < arr.size(); ++i){
        cout << arr[i] << " ";
    }
    cout<<endl;
}



// 链表结点
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}

// 二叉树--孩子兄弟表示法
//Definition for a binary tree node.// 二叉树--孩子兄弟表示法
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
typedef struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
}TreeNode,*Treelink;

/**
 * @brief 解题思路
 * 利用队列(FIFO, 先进先出) 进行实现。
 * 题目说的是，在时间点 t 进行一次 ping 操作，加上之前在 [t-3000, t] 范围内的 ping 操作的次数，并将次数返回。
 * 例如，例子中第一次 ping 的 t = 1， 返回 1；
 * 第二次 ping 的 t = 100, 第一次 ping 的时间点 1 在本次允许范围 [100-3000, 100] 之内，所以返回2；
 * 第三次 ping 时，前两次的 ping 都在允许范围[3000-3000, 3000] 之内，所以返回 3；
 * 第四次 ping 时，第一次 ping 的 t = 1 不在允许范围[3002-3000, 3000] 之内，所以返回 3。
 * 利用队列先进先出的特点，
 * 移除当次 ping 操作不在允许范围内的时间点，剩下的队列内保存的都是允许范围内的时间点，最后返回队列的长度，即为当前时间点 t 所有允许范围内的 ping 操作次数。
 * 
 */
class RecentCounter {
public:
    // RecentCounter() 初始化计数器，请求数为 0 。
    RecentCounter() {
        
    }
    //  在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，
    // 并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
    int ping(int t) {
        // 当前的先加入
        m_queue.push(t);
        while(!m_queue.empty()){
            // 获取最开头放进队列的值
            int time = m_queue.front();
            if(time < t - 3000) {
                m_queue.pop();
            } else {
                break;
            }
        }
        return m_queue.size();
    }
private:
    queue<int> m_queue;
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * RecentCounter* obj = new RecentCounter();
 * int param_1 = obj->ping(t);
 */


int main(int argc, const char** argv) {
    RecentCounter* obj = new RecentCounter();
    cout << obj->ping(1) << endl;
    cout << obj->ping(100) << endl;
    cout << obj->ping(3001) << endl;
    cout << obj->ping(3002) << endl;
    
    int target = 7;
    vector<int> nums = {2,3,1,2,4,3};
    time_t start = time(NULL);
    cout << "start time is " << start << endl;

    // cout << solu.minSubArrayLen(target, nums) << endl;
    
    time_t end = time(NULL);
    cout << "end time is " << start << endl;
    cout << "耗时：" << end*100-start*100 << " s." <<endl;


    return 0;
}